package leetcode.primary;

import java.util.HashMap;
import java.util.Map;

public class T146 {
    public int capacity;
    public Map<Integer,DoubleLikedListNode> map;
    public DoubleLinkedList list;
    public int size;
    public T146(int capacity) {
        this.capacity = capacity;
        size = 0;
        map = new HashMap<>(capacity);
        list = new DoubleLinkedList(capacity);
    }


    public int get(int key) {
        DoubleLikedListNode node = map.get(key);
        if (node==null){
            return -1;
        }
        list.removeToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)){
            map.get(key).val = value;
            list.removeToHead(map.get(key));
        }else {
            if (size>=capacity){
                System.out.println("超过容量，删除最近最少使用的");
                //删掉最近最少使用的
                DoubleLikedListNode lastPre = list.tail.pre;
                list.removeNode(lastPre);
                map.remove(lastPre.key);
                size--;
            }
            //将新结点加入map和list
            DoubleLikedListNode node = new DoubleLikedListNode(key,value);
            map.put(key,node);
            list.addNode(node);
            size++;
        }

    }
    public static void main(String[] args) {
        T146 t146 = new T146(3);
        t146.put(1,1);
        t146.put(2,2);
        t146.put(3,3);

        DoubleLikedListNode node = t146.list.head;
        while (node.next!=t146.list.tail){
            node= node.next;
            System.out.print(node.val+" ");
        }
        System.out.println();


        t146.put(4,4);
        node = t146.list.head;
        while (node.next!=t146.list.tail){
            node= node.next;
            System.out.print(node.val+" ");
        }
        System.out.println();

        System.out.println(t146.get(1));
    }
}

class DoubleLinkedList{
    public int capacity;
    public DoubleLikedListNode head;
    public DoubleLikedListNode tail;

    public DoubleLikedListNode getHead() {
        return head;
    }

    public DoubleLikedListNode getTail() {
        return tail;
    }

    public DoubleLinkedList(int capacity) {
        this.capacity = capacity;
        head = new DoubleLikedListNode();
        tail = new DoubleLikedListNode();
        head.next = tail;
        head.pre = null;
        tail.pre = head;
        tail.next = null;
    }

    public void removeNode(DoubleLikedListNode node){
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }

    public void removeToHead(DoubleLikedListNode node){
        removeNode(node);
        addNode(node);
    }
    public void addNode(DoubleLikedListNode node){
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
    }

}

class DoubleLikedListNode{
    int key;
    int val;
    DoubleLikedListNode pre;
    DoubleLikedListNode next;

    public DoubleLikedListNode() {
    }

    public DoubleLikedListNode(int key,int val, DoubleLikedListNode pre, DoubleLikedListNode next) {
        this.key = key;
        this.val = val;
        this.pre = pre;
        this.next = next;
    }

    public DoubleLikedListNode(int key,int val) {
        this.key = key;
        this.val = val;
    }
}

